package com.java.comprehensive.arithmetic.leecode.tags.tree;

import cn.hutool.core.util.ArrayUtil;
import util.TreeNode;

import java.util.*;

/**
 * @Author: Dgg
 * @Date: 2021/12/28 20:00
 */
public class LeetCode_144 {

	public static List<Integer> preorderTraversal(TreeNode root) {
		List<Integer> list = new ArrayList<>();
		if (root == null) {
			return list;
		}
		getTree(root, list);
		return list;
	}

	public static void getTree(TreeNode root, List<Integer> list) {
		if (root == null) {
			return;
		}
		list.add(root.val);
		getTree(root.left, list);
		getTree(root.right, list);

	}

	public static List<Integer> preorderTraversalTwo(TreeNode root) {
		List<Integer> res = new ArrayList<Integer>();
		if (root == null) {
			return res;
		}

		Deque<TreeNode> stack = new LinkedList<TreeNode>();
		TreeNode node = root;
		while (!stack.isEmpty() || node != null) {
			while (node != null) {
				res.add(node.val);
				stack.push(node);
				node = node.left;
			}
			node = stack.pop();
			node = node.right;
		}
		return res;
	}

	public static void main(String[] args) {
		TreeNode treeNode8 = new TreeNode(15, null, null);
		TreeNode treeNode9 = new TreeNode(4, null, treeNode8);
		TreeNode treeNode3 = new TreeNode(2, new TreeNode(1), null);
		TreeNode treeNode4 = new TreeNode(3, new TreeNode(2), treeNode9);
		TreeNode treeNode = new TreeNode(2, treeNode3, treeNode4);
		List<Integer> integers = preorderTraversal(treeNode);
		System.out.println(ArrayUtil.toString(integers));

	}

}
